#include <iostream>
#include <algorithm>
#include "TestSortHelper.h"
#include "SelectionSort.h"
#include "InsertSort.h"
#include "BubbleSort.h"

using namespace std;

template <typename T>
void shellSort(T arr[], int n) {

	int h = 1;
	while (h < n/3) {
		h = 3 * h + 1;
	}
	while (h >= 1) {

		for (int i = h;i < n;i++) {

			T temple = arr[i];
			int j = i;
			for (;j > h && temple < arr[j - h];j -= h) {
				arr[j] = arr[j - h];
			}
			arr[j] = temple;
		}
		h /= 3;
	}
}

int main(){
	int n = 10000;
	cout << "Test for Random Array, size = " << n << ", randome range [0, " << n << "]" << endl;
	int *arr1 = TestSortHelper::generateRandomArray(n, 0, n);
	int *arr2 = TestSortHelper::copyIntArray(arr1, n);
	int *arr3 = TestSortHelper::copyIntArray(arr1, n);
	int *arr4 = TestSortHelper::copyIntArray(arr1, n);
	TestSortHelper::testSort("selection Sort", selectionSort, arr1, n);
	TestSortHelper::testSort("put Sort", insertSort, arr2, n);
	TestSortHelper::testSort("bubble Sort", bubbleSort, arr3, n);
	TestSortHelper::testSort("shell Sort", bubbleSort, arr4, n);

	delete[] arr1;
	delete[] arr2;
	delete[] arr3;
	delete[] arr4;


	n = 10000;
	cout << "Test for Nearly Ordered Array, size = " << n << ", randome range [0, " << n << "]" << endl;
	arr1 = TestSortHelper::generateNearlyOrderedArray(n, 100);
	arr2 = TestSortHelper::copyIntArray(arr1, n);
	arr3 = TestSortHelper::copyIntArray(arr1, n);
	arr4 = TestSortHelper::copyIntArray(arr1, n);
	TestSortHelper::testSort("selection Sort", selectionSort, arr1, n);
	TestSortHelper::testSort("put Sort", insertSort, arr2, n);
	TestSortHelper::testSort("bubble Sort", bubbleSort, arr3, n);
	TestSortHelper::testSort("shell Sort", shellSort, arr4, n);

	delete[] arr1;
	delete[] arr2;
	delete[] arr3;
	delete[] arr4;
}